// Created by WXX on 2021/11/29 10:17
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了89.26%的用户
 * 内存消耗：8.1 MB, 在所有 C++ 提交中击败了81.11%的用户
 */
class Solution {
public:

    const double eps = 1e-8;
    int A, B;

    // 双指针算法
    int get(vector<int> &arr, double mid) {

        int res = 0;
        for (int i = 0, j = 0; i < arr.size(); i++) {
            while ((double)arr[j + 1] / arr[i] <= mid) j++;
            if ((double)arr[j] / arr[i] <= mid) res += j + 1;

            if (fabs((double)arr[j] / arr[i] - mid) < eps) {
                A = arr[j], B = arr[i];
            }
        }
        return res;
    }

    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {

        double l = 0, r = 1;
        while (r - l > eps) {
            double mid = (l + r) / 2;
            if (get(arr, mid) >= k) r = mid;
            else l = mid;
        }

        get(arr, r);
        return {A, B};
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> arr = {1, 2, 3, 5};
    OutputBasicArray1D(Solution().kthSmallestPrimeFraction(arr, 3));

    return 0;
}
